//
// Created by xili on 2024/9/11 9:20.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    int cuttingBamboo(int n) {
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        int mod = 1000000007;
        int tail = n % 3 == 0 ? 1 : (n % 3 == 1 ? 4 : 2);
        int p = (tail == 1 ? n : (n - tail)) / 3;
        return (int) (power(3, p, mod) * tail % mod);
    }

    //乘法快速幂
    long power(long long x, int n, int mod) {
        long long res = 1;
        while (n) {
            if (n & 1) {
                res = (res * x) % mod;
            }
            x = (x * x) % mod;
            n >>= 1;
        }
        return res;
    }
};